// 给定一个二叉树，在树的最后一行找到最左边的值。
// 思路，前序遍历
// 就是找最大深度的叶子节点
function findBottomLeftValue(root) {
    let result
    let maxDepth = 0
    function dfs(root, depth) {
        if (!root.left && !root.right) {
            if (depth > maxDepth) {
                maxDepth = depth
                result = root.val
                return
            }
        }
        root.left && dfs(root.left, depth + 1)
        root.right && dfs(root.right, depth + 1)
    }
    dfs(root, 1)
    return result
}

// 思路2，迭代,层序遍历
function findBottomLeftValue2(root) {
    let queue = [root]
    let result = null
    while (queue.length) {
        let len = queue.length
        result = queue[0].val
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return result
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
            left: {
                val: 1
            }
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(findBottomLeftValue(root))
console.log(findBottomLeftValue2(root))